package org.example.algorithm.graph;

import java.util.LinkedList;
import java.util.Queue;

public class AroundAreaBfsSolution {
    public void solve(char[][] board) {
        if (board == null || board.length==0) {
            return;
        }
        int row = board.length;
        int column = board[0].length;
        if (row<=2 || column<=2) {
            return;
        }
        Queue<int[]> queue = new LinkedList<>();
        for (int i=0;i<row;i++) {
            if (board[i][0] == 'O') {
                queue.offer(new int[] {i, 0});
            }
            if (board[i][column-1] == 'O') {
                queue.offer(new int[] {i, column-1});
            }
        }
        for (int j=0;j<column;j++) {
            if (board[0][j] == 'O') {
                queue.offer(new int[] {0, j});
            }
            if (board[row-1][j] == 'O') {
                queue.offer(new int[] {row-1, j});
            }
        }
        while(!queue.isEmpty()) {
            int[] item = queue.poll();
            int r = item[0];
            int c = item[1];
            board[r][c] = 'F';
            if (r > 1 && board[r-1][c] == 'O') {
                queue.offer(new int[]{r-1, c});
            }
            if (r < board.length-1 && board[r+1][c] == 'O') {
                queue.offer(new int[]{r+1, c});
            }

            if (c > 1 && board[r][c-1] == 'O') {
                queue.offer(new int[]{r, c-1});
            }
            if (c < board[0].length-1 && board[r][c+1] == 'O') {
                queue.offer(new int[]{r, c+1});
            }
        }

        for (int i=0;i<row;i++) {
            for (int j=0;j<column;j++) {
                if (board[i][j] == 'F') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public static void main(String[] args) {
        //char[][] board = {{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};
        char[][] board = {{'O','X','X','O','X'},{'X','O','O','X','O'},{'X','O','X','O','X'},{'O','X','O','O','O'},{'X','X','O','X','O'}};
        AroundAreaBfsSolution aroundAreaSolution = new AroundAreaBfsSolution();
        aroundAreaSolution.solve(board);
        for (int i=0;i<board.length;i++) {
            for (int j=0;j<board[0].length;j++) {
                System.out.print(board[i][j]);
            }
            System.out.println("");
        }
    }
}
